package leetcode.graph;

import java.util.LinkedList;

/**
 * @author wangmaolin1
 * @date 2023/11/12 23:05
 */
public class _277 {
    /**
     * 监测名人
     * 名人不认识其他任何人，其他人都认识名人
     * @param n
     * @return
     */
    int findCelebrity(int n) {
        if (n == 1) {
            return 0;
        }
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.addLast(i);
        }
        while (list.size() >= 2) {
            int cand = list.removeFirst();
            int other = list.removeFirst();
            if (knows(cand, other) || !knows(other, cand)) {
                list.offer(other);
            } else {
                list.offer(cand);
            }
        }
        Integer cand = list.removeFirst();
        for (int i = 0; i < n; i++) {
            if (knows(cand, n) || !knows(i, cand)) {
                return -1;
            }
        }
        return cand;
    }

    // 已有的函数，返回i是否认识j
    boolean knows(int i, int j) {
        return true;
    }
}
